package 快速排序;
/*
 快速排序
- 将排序范围中的第一个数字作为基准数，再定义两个变量start，end
- start从前往后找比基准数大的，end从后往前找比基准数小的。
- 找到之后交换start和end指向的元素，并循环这一过程，直到start和end处于同一个位置，该位置是基准数在数组中应存入的位置，再让基准数归位。
- 归位后的效果：基准数左边的，比基准数小，基准数右边的，比基准数大
*/
public class QuickSortDemo {
    public static void main(String[] args) {
        //快速排序:
        //第一轮：以0索引的数字为基准数，确定基准数在数组中正确的位置
        //比基准数小的全部在左边，比基准数大的全部在右边
        //后面以此类推
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        quickSort(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    public static void quickSort(int []arr,int i,int j){
        int star=i;
        int end=j;
        //递归出口
        if(star>end)
            return;
        int number=arr[i];
        while(star!=end){
            //从后往前找比基准数小的数
            while(true)
            {
                if(end<=star||arr[end]<number)//先从后面找
                {
                    break;
                }
                end--;
            }
            //从前往后找比基准数大的数
            while(true){
                if(end<=star||arr[star]>number)
                {
                    break;
                }
                star++;
            }
            //交换元素
            int tmp=arr[star];
            arr[star]=arr[end];
            arr[end]=tmp;
        }
        //基准数归位
        int tmp=arr[i];
        arr[i]=arr[end];
        arr[end]=tmp;
        //递归
        quickSort(arr,0,star-1);
        quickSort(arr,star+1,j);
    }
}
